The present invention generally relates to stochastic networks, and more particularly, implementation of stochastic network solutions in the analysis, modeling and optimization of multi-resource applications.
Stochastic networks have played a fundamental role as canonical models for a wide variety of multi-resource applications. Examples include business process management (WBM), computer capacity planning, manufacturing systems, multi-item inventory systems, call centers, and workforce management systems. Companies are investing in methodologies to determine the “best” resource capacities to satisfy the forecasted demand in these multi-resource applications.
Currently there are many methodologies based solely on simple analytic models, the assumptions of which often do not hold, and for which no bounds on errors can be calculated (e.g., computer capacity planning). Some methodologies are based solely on black-box use of simulation, which can be computationally expensive and require many iterations (e.g., OptTek; refer to http://www.opttek.com/). Moreover, there are few if any methodologies for managing structures in stochastic networks by choosing the most appropriate, such as the topology of the network and policies for resource sharing.
Stochastic networks have played a fundamental role as canonical models for a wide variety of multi-resource applications, including numerous types of computer and communication systems, manufacturing systems, multi-item inventory systems, call centers, and workforce management systems. The complexity of such applications continue to grow at a rapid pace, which in turn increases the technical difficulties of obtaining stochastic network solutions in the analysis, modeling and optimization of these applications. Moreover, the consistent stream of emerging multi-resource application areas continues to further exacerbate this growth trend in complexity.
One particularly important example is business performance management, which is a key emerging technology positioned to enable optimization of business process operations and information technology infrastructure through stochastic network models in order to achieve business performance targets.
There currently exists methodologies based solely on simple analytic models, the assumptions of which do not hold and for which there are no bounds on errors (e.g., computer capacity planning).
The primary difficulty in obtaining stochastic network solutions in the analysis, modeling and optimization of multi-resource applications concerns the complex dependencies among the processing stations, or queues, in the network. Indeed, it is only under relatively strong restrictions that the stationary joint distribution for the network has a product four in terms of the stationary distribution for each queue in isolation. Although the requirements for product-form solutions may not often hold in practice, the use of these results as approximations, possibly together with other heuristics, is a frequently employed approach in computer capacity planning applications. However, the accuracy of this approach, in the absence of any bounds on the errors, is an important concern from both a theoretical and practical perspective. Due to the difficulty of obtaining analytic solutions for non-product-form stochastic networks, alternative approaches are often based on various forms of stochastic simulation methods. In particular, there is essentially exclusive use of simulation for the analysis, modeling and optimization of stochastic network models of business processes, with few exceptions.
On the other hand, there are current methodologies that are based solely on black-box use of simulation, which can be computationally expensive, especially when used to solve optimization problems involving multidimensional stochastic systems and require many iterations (OptTek). Simulation-based techniques have been widely studied to address such stochastic optimization problems in general.
Of particular interest from both theoretical and practical perspectives are Brownian models of feedforward stochastic networks and non-linear optimization based on convex programming and trust region methods. Under the latter iterative methods, the objective function is approximated in a neighborhood of the current iterate (the so-called “trust region”) by a surrogate model that is “easier” to deal with than the objective function; see, e.g., A. R. Conn, N. I. M. Gould, P. L. Toint. Trust-Region Methods, SIAM, 2000. The iterative procedure moves to the next iterate within the trust region that optimizes the surrogate model, where both the trust region and surrogate model are updated as more information about the true objective function is obtained.
State-of-art for trust-region methods are based on a black-box approach in which the structure and properties underlying the stochastic network are ignored.
There currently does not exist an approach for managing capacities and structures in stochastic networks, such as the topology of the network and policies for resource sharing.